package 数组;
import java.util.*;
/**
 * 寻找数组中的多数元素（出现次数超过数组长度一半的元素）
 * 提供了三种不同的实现方法：哈希表、排序和投票算法
 */
public class majorityElement {
    /**
     * 使用哈希表方法查找多数元素
     * 时间复杂度：O(n)，空间复杂度：O(n)
     * 
     * @param nums 输入数组
     * @return 多数元素，如果不存在则返回-1
     */
    public int majorHash(int[] nums){
        HashMap<Integer, Integer> map = new HashMap<>(); // 创建哈希表存储每个元素出现的次数
        for(int i = 0; i < nums.length; i++){ // 遍历数组统计每个元素出现的次数
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int mid = nums.length >> 1; // 计算数组长度的一半
        for(int key : map.keySet()){ // 遍历哈希表查找出现次数超过一半的元素
            if(map.get(key) > mid) return key; 
        }
        return -1; // 如果没有找到多数元素，返回-1
    }

    /**
     * 使用排序方法查找多数元素
     * 时间复杂度：O(nlogn)，空间复杂度：O(1)
     * 
     * @param nums 输入数组
     * @return 多数元素（排序后数组中间的元素）
     */
    public int majorSort(int[] nums){
        // Arrays.sort(nums); // 使用Java内置的排序方法
        quickSort(nums, 0, nums.length - 1); // 使用快速排序对数组进行排序
        return nums[nums.length >> 1]; // 返回排序后数组中间的元素
    }

    /**
     * 快速排序算法
     * 
     * @param nums 待排序的数组
     * @param left 左边界
     * @param right 右边界
     */
    private void quickSort(int[] nums, int left, int right){
        if(left >= right) return; // 如果左边界大于等于右边界，则返回
        int pivot = partition(nums, left, right); // 获取基准元素的位置
        quickSort(nums, left, pivot - 1); // 对左半部分进行快速排序
        quickSort(nums, pivot + 1, right); // 对右半部分进行快速排序
    }

    /**
     * 快速排序的分区操作
     * 
     * @param nums 待分区的数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的最终位置
     */
    private int partition(int[] nums, int left, int right){
        int val = nums[left]; // 选择左边界元素作为基准值
        while(left < right){ // 当左右指针相遇时结束
            while(left < right && nums[right] >= val) right--; // 从右向左找到第一个小于基准值的元素
            nums[left] = nums[right]; // 将找到的元素放到左边界
            while(left < right && nums[left] <= val) left++; // 从左向右找到第一个大于基准值的元素
            nums[right] = nums[left]; // 将找到的元素放到右边界
        }
        nums[left] = val; // 将基准值放到最终位置
        return left; // 返回基准值的最终位置
    }

    /**
     * 使用投票算法查找多数元素
     * 时间复杂度：O(n)，空间复杂度：O(1)
     * 
     * @param nums 输入数组
     * @return 多数元素
     */
    public int majorVote(int[] nums){
        int major = 0; // 候选多数元素
        int vote = 0; // 投票计数器
        for(int num : nums){ // 遍历数组
            if(vote == 0) // 如果投票数为0，更新候选元素
                major = num;
            if(major == num) // 如果当前元素等于候选元素，投票数加1
                vote++;
            else // 否则投票数减1
                vote--;
        }
        return major; // 返回候选元素
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用逗号分隔，表示输入数组
     * 输出格式：三种方法找到的多数元素
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(","); // 读取输入并分割
        int[] nums = new int[s.length]; // 创建输入数组
        for(int i = 0; i < s.length; i++){ // 将输入转换为整数数组
            nums[i] = Integer.parseInt(s[i]); // 将字符串转换为整数
        }
        majorityElement me = new majorityElement(); // 创建实例
        System.out.println("hash:" + me.majorHash(nums)); // 输出哈希表方法的结果
        System.out.println("sort:" + me.majorSort(nums)); // 输出排序方法的结果
        System.out.println("vote:" + me.majorVote(nums)); // 输出投票算法的结果
        sc.close(); // 关闭输入流
    }
}
